{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Connected Components\n",
    "\n",
    "In this notebook, we will use cuGraph to compute weakly and strongly connected components of a graph and display some useful information about the resulting components.\n",
    "\n",
    "_Weakly connected component_ (WCC) is often a necessary pre-processing step for many graph algorithms. A dataset may contact several disconnected (sub-) graphs.  Quite often, running a graph algorithm only on one component of a disconnected graph can lead to bugs which are not easy to trace.\n",
    "\n",
    "_Strongly connected components_ (SCC) is used in the early stages of graph analysis to get an idea of a graph's structure.\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "Notebook Credits\n",
    "* Original Authors: Kumar Aatish\n",
    "* Created:    08/13/2019\n",
    "* Last Edit:  03/03/2020\n",
    "\n",
    "RAPIDS Versions: 0.13   \n",
    "\n",
    "Test Hardware\n",
    "\n",
    "* GV100 32G, CUDA 10.2\n",
    "\n",
    "\n",
    "\n",
    "## Introduction\n",
    "\n",
    "### Weakly Connected Components\n",
    "To compute WCC for a graph in cuGraph we use:\n",
    "\n",
    "**cugraph.weakly_connected_components(G)**\n",
    "\n",
    "   Generate the weakly connected components and attach a component label to each vertex.\n",
    "\n",
    "    Parameters\n",
    "    ----------\n",
    "    G : cugraph.Graph\n",
    "        cuGraph graph descriptor, should contain the connectivity information\n",
    "        as an edge list (edge weights are not used for this algorithm).\n",
    "        Currently, the graph should be undirected where an undirected edge is\n",
    "        represented by a directed edge in both directions. The adjacency list\n",
    "        will be computed if not already present. The number of vertices should\n",
    "        fit into a 32b int.\n",
    "\n",
    "    Returns\n",
    "    -------\n",
    "    df : cudf.DataFrame\n",
    "      df['labels'][i] gives the label id of the i'th vertex\n",
    "      df['vertices'][i] gives the vertex id of the i'th vertex\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "### Strongly Connected Components\n",
    "To compute SCC for a graph in cuGraph we use:\n",
    "\n",
    "**cugraph.strongly_connected_components(G)**\n",
    "\n",
    "\n",
    "    Generate the stronlgly connected components and attach a component label to each vertex.\n",
    "\n",
    "    Parameters\n",
    "    ----------\n",
    "    G : cugraph.Graph\n",
    "      cuGraph graph descriptor, should contain the connectivity information as\n",
    "      an edge list (edge weights are not used for this algorithm). The graph\n",
    "      can be either directed or undirected where an undirected edge is\n",
    "      represented by a directed edge in both directions.\n",
    "      The adjacency list will be computed if not already present.\n",
    "      The number of vertices should fit into a 32b int.\n",
    "\n",
    "    Returns\n",
    "    -------\n",
    "    df : cudf.DataFrame\n",
    "      df['labels'][i] gives the label id of the i'th vertex\n",
    "      df['vertices'][i] gives the vertex id of the i'th vertex\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## cuGraph Notice \n",
    "The current version of cuGraph has some limitations:\n",
    "\n",
    "* Vertex IDs need to be 32-bit integers.\n",
    "* Vertex IDs are expected to be contiguous integers starting from 0.\n",
    "\n",
    "cuGraph provides the renumber function to mitigate this problem. Input vertex IDs for the renumber function can be either 32-bit or 64-bit integers, can be non-contiguous, and can start from an arbitrary number. The renumber function maps the provided input vertex IDs to 32-bit contiguous integers starting from 0. cuGraph still requires the renumbered vertex IDs to be representable in 32-bit integers. These limitations are being addressed and will be fixed soon."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Test Data\n",
    "We will be using the Netscience dataset :  \n",
    "*M. E. J. Newman, Finding community structure in networks using the eigenvectors of matrices, Preprint physics/0605087 (2006)*\n",
    "\n",
    "The graph netscience contains a coauthorship network of scientists working on network theory and experiment. The version given here contains all components of the network, for a total of 1589 scientists, with the the largest component of 379 scientists.\n",
    "\n",
    "Netscience Adjacency Matrix               |NetScience Strongly Connected Components\n",
    ":---------------------------------------------|------------------------------------------------------------:\n",
    "![](../img/netscience.png \"Credit : https://www.cise.ufl.edu/research/sparse/matrices/Newman/netscience\") | ![](../img/netscience_scc.png \"Credit : https://www.cise.ufl.edu/research/sparse/matrices/Newman/netscience\")\n",
    "  \n",
    "Matrix plots above by Yifan Hu, AT&T Labs Visualization Group."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Import needed libraries\n",
    "import cugraph\n",
    "import cudf\n",
    "import numpy as np\n",
    "from collections import OrderedDict"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1. Read graph data from file\n",
    "\n",
    "cuGraph depends on cuDF for data loading and the initial Dataframe creation on the GPU.\n",
    "\n",
    "The data file contains an edge list, which represents the connection of a vertex to another. The source to destination pairs is in what is known as Coordinate Format (COO).\n",
    "\n",
    "In this test case the data in the test file is expressed in three columns, source, destination and the edge weight. While edge weight is relevant in other algorithms, cuGraph connected component calls do not make use of it and hence that column can be discarded from the dataframe."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>src</th>\n",
       "      <th>dst</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>1084</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>946</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>1084</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>3</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "    src  dst\n",
       "0     1    0\n",
       "1  1084    0\n",
       "2   946    1\n",
       "3  1084    1\n",
       "4     3    2"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Test file\n",
    "datafile='../data/netscience.csv'\n",
    "\n",
    "# the datafile contains three columns,but we only want to use the first two. \n",
    "# We will use the \"usecols' feature of read_csv to ignore that column\n",
    "\n",
    "gdf = cudf.read_csv(datafile, delimiter=' ', names=['src', 'dst', 'wgt'], dtype=['int32', 'int32', 'float32'], usecols=['src', 'dst'])\n",
    "gdf.head()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2. Create a Graph from an edge list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# create a Graph using the source (src) and destination (dst) vertex pairs from the Dataframe\n",
    "G = cugraph.Graph()\n",
    "G.from_cudf_edgelist(gdf, source='src', destination='dst')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3a. Call Weakly Connected Components"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>labels</th>\n",
       "      <th>vertices</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>3</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>3</td>\n",
       "      <td>3</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>3</td>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   labels  vertices\n",
       "0       1         0\n",
       "1       1         1\n",
       "2       3         2\n",
       "3       3         3\n",
       "4       3         4"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Call cugraph.weakly_connected_components on the dataframe\n",
    "df = cugraph.weakly_connected_components(G)\n",
    "df.head()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Get total number of weakly connected components"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Total number of components found :  268\n"
     ]
    }
   ],
   "source": [
    "# Use groupby on the 'labels' column of the WCC output to get the counts of each connected component label\n",
    "label_gby = df.groupby('labels')\n",
    "label_count = label_gby.count()\n",
    "\n",
    "print(\"Total number of components found : \", len(label_count))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Get size of the largest weakly connected component"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Size of the largest component is found to be :  379\n"
     ]
    }
   ],
   "source": [
    "# Call nlargest on the groupby result to get the row where the component count is the largest\n",
    "largest_component = label_count.nlargest(n = 1, columns = 'vertices')\n",
    "print(\"Size of the largest component is found to be : \", largest_component['vertices'][0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Output vertex ids belonging to a weakly connected component label"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Vertex Ids that belong to component label 1 : \n",
      "      labels  vertices\n",
      "0          1         0\n",
      "1          1         1\n",
      "883        1       883\n",
      "1009       1      1009\n"
     ]
    }
   ],
   "source": [
    "# Query the connected component output to display vertex ids that belong to a component of interest\n",
    "expr = \"labels == 1\"\n",
    "component = df.query(expr)\n",
    "print(\"Vertex Ids that belong to component label 1 : \")\n",
    "print(component)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3b. Call Strongly Connected Components"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>labels</th>\n",
       "      <th>vertices</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>2</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>2</td>\n",
       "      <td>3</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>2</td>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   labels  vertices\n",
       "0       0         0\n",
       "1       0         1\n",
       "2       2         2\n",
       "3       2         3\n",
       "4       2         4"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Call cugraph.strongly_connected_components on the dataframe\n",
    "df = cugraph.strongly_connected_components(G)\n",
    "df.head()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Get total number of strongly connected components"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Total number of components found :  268\n"
     ]
    }
   ],
   "source": [
    "# Use groupby on the 'labels' column of the SCC output to get the counts of each connected component label\n",
    "label_gby = df.groupby('labels')\n",
    "label_count = label_gby.count()\n",
    "print(\"Total number of components found : \", len(label_count))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Get size of the largest strongly connected component"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Size of the largest component is found to be :  379\n"
     ]
    }
   ],
   "source": [
    "# Call nlargest on the groupby result to get the row where the component count is the largest\n",
    "largest_component = label_count.nlargest(n = 1, columns = 'vertices')\n",
    "print(\"Size of the largest component is found to be : \", largest_component['vertices'][0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Output vertex ids belonging to a strongly connected component label"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Vertex Ids that belong to component label 2 : \n",
      "   labels  vertices\n",
      "2       2         2\n",
      "3       2         3\n",
      "4       2         4\n",
      "5       2         5\n",
      "6       2         6\n"
     ]
    }
   ],
   "source": [
    "# Query the connected component output to display vertex ids that belong to a component of interest\n",
    "expr = \"labels == 2\"\n",
    "component = df.query(expr)\n",
    "print(\"Vertex Ids that belong to component label 2 : \")\n",
    "print(component)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Conclusion\n",
    "\n",
    "The number of components found by **cugraph.weakly_connected_components(G)** and **cugraph.strongly_connected_components(G)** are equal to the results from  M. E. J. Newman,\n",
    "Phys. Rev. E 64, 016132 (2001)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "___\n",
    "Copyright (c) 2019, NVIDIA CORPORATION.\n",
    "\n",
    "Licensed under the Apache License, Version 2.0 (the \"License\");  you may not use this file except in compliance with the License. You may obtain a copy of the License at http://www.apache.org/licenses/LICENSE-2.0\n",
    "\n",
    "Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an \"AS IS\" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.\n",
    "___"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "cugraph_dev",
   "language": "python",
   "name": "cugraph_dev"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
